<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <script>
            var findItinerary = function (tickets) {
                let map = new Map()
                const res = ["JFK"]
                for (let i = 0; i < tickets.length; i++) {
                    let [from, to] = tickets[i]
                    if (!map.has(from)) {
                        map.set(from, [])
                    }
                    map.get(from).push(to)
                }
                for (let [key, value] of map) {
                    value.sort()
                }

                function backTracking() {
                    if (res.length == tickets.length + 1) {
                        return true
                    }
                    //机票未用完,找后面可去往的城市
                    let nextCities = map.get(res[res.length - 1])
                    if (!nextCities || !nextCities.length) return false
                    for (let i = 0; i < nextCities.length; i++) {
                        let city = nextCities[i]
                        res.push(city)
                        nextCities.splice(i, 1)
                        if (backTracking()) return true
                        res.pop()
                        nextCities.splice(i, 0, city)
                    }
                }
                backTracking()
                return res
            }
        </script>
    </body>
</html>
